{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Please input the size of population: \n",
      "Please input the size of Crossover Rate: \n",
      "Please input the size of Mutation Rate: \n",
      "Please input the mutation selection rate: \n",
      "Please input number of iteration: \n",
      "optimal sequence [3, 1, 5, 3, 5, 5, 5, 4, 6, 0, 1, 1, 7, 6, 9, 6, 9, 8, 9, 8, 4, 3, 8, 1, 4, 9, 6, 4, 8, 5, 6, 9, 6, 4, 6, 0, 0, 0, 9, 3, 7, 6, 1, 0, 6, 2, 3, 2, 8, 3, 0, 8, 4, 9, 8, 4, 1, 2, 6, 0, 5, 8, 7, 7, 4, 7, 2, 5, 2, 0, 2, 5, 8, 4, 2, 1, 9, 7, 8, 1, 7, 7, 3, 5, 3, 9, 1, 0, 0, 2, 7, 2, 1, 7, 5, 9, 4, 2, 3, 3]\n",
      "optimal value:1167.000000\n",
      "the elapsed time:38.7791645526886\n"
     ]
    }
   ],
   "source": [
    "# -*- coding: utf-8 -*-\n",
    "\"\"\"\n",
    "Created on Fri Jul 13 17:24:51 2018\n",
    "\n",
    "Author: cheng-man wu\n",
    "LinkedIn: www.linkedin.com/in/chengmanwu\n",
    "Github: https://github.com/wurmen\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "'''==========Solving job shop scheduling problem by gentic algorithm in python======='''\n",
    "# importing required modules\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "import time\n",
    "import copy\n",
    "\n",
    "''' ================= initialization setting ======================'''\n",
    "\n",
    "\n",
    "pt_tmp=pd.read_excel(\"JSP_dataset.xlsx\",sheet_name=\"Processing Time\",index_col =[0])\n",
    "ms_tmp=pd.read_excel(\"JSP_dataset.xlsx\",sheet_name=\"Machines Sequence\",index_col =[0])\n",
    "\n",
    "dfshape=pt_tmp.shape\n",
    "num_mc=dfshape[1] # number of machines\n",
    "num_job=dfshape[0] # number of jobs\n",
    "num_gene=num_mc*num_job # number of genes in a chromosome\n",
    "\n",
    "pt=[list(map(int, pt_tmp.iloc[i])) for i in range(num_job)]\n",
    "ms=[list(map(int,ms_tmp.iloc[i])) for i in range(num_job)]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# raw_input is used in python 2\n",
    "population_size=int(input('Please input the size of population: ') or 30) # default value is 30\n",
    "crossover_rate=float(input('Please input the size of Crossover Rate: ') or 0.8) # default value is 0.8\n",
    "mutation_rate=float(input('Please input the size of Mutation Rate: ') or 0.2) # default value is 0.2\n",
    "mutation_selection_rate=float(input('Please input the mutation selection rate: ') or 0.2)\n",
    "num_mutation_jobs=round(num_gene*mutation_selection_rate)\n",
    "num_iteration=int(input('Please input number of iteration: ') or 2000) # default value is 2000\n",
    "    \n",
    "start_time = time.time()\n",
    "\n",
    "'''==================== main code ==============================='''\n",
    "'''----- generate initial population -----'''\n",
    "Tbest=999999999999999\n",
    "best_list,best_obj=[],[]\n",
    "population_list=[]\n",
    "for i in range(population_size):\n",
    "    nxm_random_num=list(np.random.permutation(num_gene)) # generate a random permutation of 0 to num_job*num_mc-1\n",
    "    population_list.append(nxm_random_num) # add to the population_list\n",
    "    for j in range(num_gene):\n",
    "        population_list[i][j]=population_list[i][j]%num_job # convert to job number format, every job appears m times\n",
    "        \n",
    "for n in range(num_iteration):\n",
    "    Tbest_now=99999999999           \n",
    "   \n",
    "    '''-------- two point crossover --------'''\n",
    "    parent_list=copy.deepcopy(population_list)\n",
    "    offspring_list=copy.deepcopy(population_list)\n",
    "    S=list(np.random.permutation(population_size)) # generate a random sequence to select the parent chromosome to crossover\n",
    "    \n",
    "    for m in range(int(population_size/2)):\n",
    "        crossover_prob=np.random.rand()\n",
    "        if crossover_rate>=crossover_prob:\n",
    "            parent_1= population_list[S[2*m]][:]\n",
    "            parent_2= population_list[S[2*m+1]][:]\n",
    "            child_1=parent_1[:]\n",
    "            child_2=parent_2[:]\n",
    "            cutpoint=list(np.random.choice(num_gene, 2, replace=False))\n",
    "            cutpoint.sort()\n",
    "        \n",
    "            child_1[cutpoint[0]:cutpoint[1]]=parent_2[cutpoint[0]:cutpoint[1]]\n",
    "            child_2[cutpoint[0]:cutpoint[1]]=parent_1[cutpoint[0]:cutpoint[1]]\n",
    "            offspring_list[S[2*m]]=child_1[:]\n",
    "            offspring_list[S[2*m+1]]=child_2[:]\n",
    "        \n",
    "    \n",
    "    '''----------repairment-------------'''\n",
    "    for m in range(population_size):\n",
    "        job_count={}\n",
    "        larger,less=[],[] # 'larger' record jobs appear in the chromosome more than m times, and 'less' records less than m times.\n",
    "        for i in range(num_job):\n",
    "            if i in offspring_list[m]:\n",
    "                count=offspring_list[m].count(i)\n",
    "                pos=offspring_list[m].index(i)\n",
    "                job_count[i]=[count,pos] # store the above two values to the job_count dictionary\n",
    "            else:\n",
    "                count=0\n",
    "                job_count[i]=[count,0]\n",
    "            if count>num_mc:\n",
    "                larger.append(i)\n",
    "            elif count<num_mc:\n",
    "                less.append(i)\n",
    "                \n",
    "        for k in range(len(larger)):\n",
    "            chg_job=larger[k]\n",
    "            while job_count[chg_job][0]>num_mc:\n",
    "                for d in range(len(less)):\n",
    "                    if job_count[less[d]][0]<num_mc:                    \n",
    "                        offspring_list[m][job_count[chg_job][1]]=less[d]\n",
    "                        job_count[chg_job][1]=offspring_list[m].index(chg_job)\n",
    "                        job_count[chg_job][0]=job_count[chg_job][0]-1\n",
    "                        job_count[less[d]][0]=job_count[less[d]][0]+1                    \n",
    "                    if job_count[chg_job][0]==num_mc:\n",
    "                        break     \n",
    "    \n",
    "    '''--------mutatuon--------'''   \n",
    "    for m in range(len(offspring_list)):\n",
    "        mutation_prob=np.random.rand()\n",
    "        if mutation_rate >= mutation_prob:\n",
    "            m_chg=list(np.random.choice(num_gene, num_mutation_jobs, replace=False)) # chooses the position to mutation\n",
    "            t_value_last=offspring_list[m][m_chg[0]] # save the value which is on the first mutation position\n",
    "            for i in range(num_mutation_jobs-1):\n",
    "                offspring_list[m][m_chg[i]]=offspring_list[m][m_chg[i+1]] # displacement\n",
    "            \n",
    "            offspring_list[m][m_chg[num_mutation_jobs-1]]=t_value_last # move the value of the first mutation position to the last mutation position\n",
    "  \n",
    "    \n",
    "    '''--------fitness value(calculate makespan)-------------'''\n",
    "    total_chromosome=copy.deepcopy(parent_list)+copy.deepcopy(offspring_list) # parent and offspring chromosomes combination\n",
    "    chrom_fitness,chrom_fit=[],[]\n",
    "    total_fitness=0\n",
    "    for m in range(population_size*2):\n",
    "        j_keys=[j for j in range(num_job)]\n",
    "        key_count={key:0 for key in j_keys}\n",
    "        j_count={key:0 for key in j_keys}\n",
    "        m_keys=[j+1 for j in range(num_mc)]\n",
    "        m_count={key:0 for key in m_keys}\n",
    "        \n",
    "        for i in total_chromosome[m]:\n",
    "            gen_t=int(pt[i][key_count[i]])\n",
    "            gen_m=int(ms[i][key_count[i]])\n",
    "            j_count[i]=j_count[i]+gen_t\n",
    "            m_count[gen_m]=m_count[gen_m]+gen_t\n",
    "            \n",
    "            if m_count[gen_m]<j_count[i]:\n",
    "                m_count[gen_m]=j_count[i]\n",
    "            elif m_count[gen_m]>j_count[i]:\n",
    "                j_count[i]=m_count[gen_m]\n",
    "            \n",
    "            key_count[i]=key_count[i]+1\n",
    "    \n",
    "        makespan=max(j_count.values())\n",
    "        chrom_fitness.append(1/makespan)\n",
    "        chrom_fit.append(makespan)\n",
    "        total_fitness=total_fitness+chrom_fitness[m]\n",
    "\n",
    "    \n",
    "    '''----------selection(roulette wheel approach)----------'''\n",
    "    pk,qk=[],[]\n",
    "    \n",
    "    for i in range(population_size*2):\n",
    "        pk.append(chrom_fitness[i]/total_fitness)\n",
    "    for i in range(population_size*2):\n",
    "        cumulative=0\n",
    "        for j in range(0,i+1):\n",
    "            cumulative=cumulative+pk[j]\n",
    "        qk.append(cumulative)\n",
    "    \n",
    "    selection_rand=[np.random.rand() for i in range(population_size)]\n",
    "    \n",
    "    for i in range(population_size):\n",
    "        if selection_rand[i]<=qk[0]:\n",
    "            population_list[i]=copy.deepcopy(total_chromosome[0])\n",
    "        else:\n",
    "            for j in range(0,population_size*2-1):\n",
    "                if selection_rand[i]>qk[j] and selection_rand[i]<=qk[j+1]:\n",
    "                    population_list[i]=copy.deepcopy(total_chromosome[j+1])\n",
    "                    break\n",
    "    '''----------comparison----------'''\n",
    "    for i in range(population_size*2):\n",
    "        if chrom_fit[i]<Tbest_now:\n",
    "            Tbest_now=chrom_fit[i]\n",
    "            sequence_now=copy.deepcopy(total_chromosome[i])\n",
    "    if Tbest_now<=Tbest:\n",
    "        Tbest=Tbest_now\n",
    "        sequence_best=copy.deepcopy(sequence_now)\n",
    "    \n",
    "'''----------result----------'''\n",
    "print(\"optimal sequence\",sequence_best)\n",
    "print(\"optimal value:%f\"%Tbest)\n",
    "print('the elapsed time:%s'% (time.time() - start_time))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<iframe id=\"igraph\" scrolling=\"no\" style=\"border:none;\" seamless=\"seamless\" src=\"https://plot.ly/~ftcu5931/50.embed\" height=\"600px\" width=\"900px\"></iframe>"
      ],
      "text/plain": [
       "<plotly.tools.PlotlyDisplay object>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'''--------plot gantt chart-------'''\n",
    "import pandas as pd\n",
    "import plotly.plotly as py\n",
    "import plotly.figure_factory as ff\n",
    "import datetime\n",
    "\n",
    "m_keys=[j+1 for j in range(num_mc)]\n",
    "j_keys=[j for j in range(num_job)]\n",
    "key_count={key:0 for key in j_keys}\n",
    "j_count={key:0 for key in j_keys}\n",
    "m_count={key:0 for key in m_keys}\n",
    "j_record={}\n",
    "for i in sequence_best:\n",
    "    gen_t=int(pt[i][key_count[i]])\n",
    "    gen_m=int(ms[i][key_count[i]])\n",
    "    j_count[i]=j_count[i]+gen_t\n",
    "    m_count[gen_m]=m_count[gen_m]+gen_t\n",
    "    \n",
    "    if m_count[gen_m]<j_count[i]:\n",
    "        m_count[gen_m]=j_count[i]\n",
    "    elif m_count[gen_m]>j_count[i]:\n",
    "        j_count[i]=m_count[gen_m]\n",
    "    \n",
    "    start_time=str(datetime.timedelta(seconds=j_count[i]-pt[i][key_count[i]])) # convert seconds to hours, minutes and seconds\n",
    "    end_time=str(datetime.timedelta(seconds=j_count[i]))\n",
    "        \n",
    "    j_record[(i,gen_m)]=[start_time,end_time]\n",
    "    \n",
    "    key_count[i]=key_count[i]+1\n",
    "        \n",
    "\n",
    "df=[]\n",
    "for m in m_keys:\n",
    "    for j in j_keys:\n",
    "        df.append(dict(Task='Machine %s'%(m), Start='2018-07-14 %s'%(str(j_record[(j,m)][0])), Finish='2018-07-14 %s'%(str(j_record[(j,m)][1])),Resource='Job %s'%(j+1)))\n",
    "    \n",
    "fig = ff.create_gantt(df, index_col='Resource', show_colorbar=True, group_tasks=True, showgrid_x=True, title='Job shop Schedule')\n",
    "py.iplot(fig, filename='GA_job_shop_scheduling1', world_readable=True)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
